package com.sj.leetcode.editor.cn.sort;

import java.util.Arrays;

/**
 * 选 基准元素， 左小 右大； 左右递归一直到元素不可再分
 * 单边循环 取一个 基准元素 p，挖坑，然后第二个往后，比
 */
public class QuickSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) { /* 递归结束条件：startIndex大等于endIndex的时候*/
        if (startIndex >= endIndex) return; /* 得到基准元素位置*/
        int pivotIndex = partition(arr, startIndex, endIndex); /* 用分治法递归数列的两部分*/
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    private static int partition(int[] arr, int startIndex, int endIndex) {/* 取第一个位置的元素作为基准元素*/
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex; /* 坑的位置，初始等于pivot的位置*/
        int index = startIndex; /*大循环在左右指针重合或者交错时结束*/
        while (right >= left) { /*right指针从右向左进行比较*/
            while (right >= left) {
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
            } /*left指针从左向右进行比较*/
            while (right >= left) {
                if (arr[left] > pivot) {
                    arr[right] = arr[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        arr[index] = pivot;
        return index;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}












//|   原则名称   |     内容说明 |
//| ---- | ---- |
//|   开闭原则   |     对扩展开放，对修改关闭。 |
//|   单一职责原则   |   即一个类只负责相应领域的职责，即不要存在多于一个导致类变更的原因。   |
//|   里氏代换原则   |   子类型必须能够替换它们的父类型。一个软件实体如果使用的是一个父类，那么当把这个父类替换成继承该父类的子类，程序的行为不会发生任何变化。软件实体察觉不出父类对象和子类对象的区别。   |
//|   依赖倒置原则   |   要依赖于抽象，不要依赖于具体。客户端依赖于抽象耦合。抽象不应当依赖于细节；细节应当依赖于抽象；要针对接口编程，不针对实现编程。   |
//|   接口隔离原则   |   客户端不应该依赖它不需要的接口。一个类对另一个类的依赖应该建立在最小的接口上。   |
//|   最少知识原则   |   对象与对象之间应该使用尽可能少的方法来关联，避免千丝万缕的关系。   |

